class Solution {
public:
        int mem[220][220];
    int getMoneyAmount(int n) {
        return dfs(1,n);
    }

    int dfs(int left,int right)
    {
        if(left>=right) return 0;
        if(mem[left][right]!=0) return mem[left][right];
        int ret=INT_MAX;
        for(int i=left;i<=right;++i)
        {
            int l=dfs(left,i-1);
            int r=dfs(i+1,right);
            ret=min(ret,i+max(l,r));
        }
        mem[left][right]=ret;
        return ret;
    }
};
